3-30 125. 验证回文串

Date：2022-03-29 21:58:19

题目：125. 验证回文串 ( 简单😄 )

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例

示例1：

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例2：

输入: "race a car"
输出: false
解释："raceacar" 不是回文串

分析

• 筛选+双指针

  先筛选出字母和数字，再利用双指针判断是否为回文串即可

  O(n), O(1)

• 比对+双指针

  直接双指针，过程中跳过不符合条件的字符

  O(n), O(1)

注意：String.replace(//g) 与 String.replaceAll(//g) 等效，有的环境下会提示replaceAll 不是一个函数，所以用replace即可

题解

替换+双指针

function isPalindrome(s: string): boolean {
  const reg = /[^a-zA-Z0-9]/g

  s = s.replace(reg, '').toLowerCase()

  let left = 0,
      right = s.length - 1
  while (left < right) {
    const charL = s.charAt(left)
    const charR = s.charAt(right)

    if (!charL || !charR) {
      return false
    }

    if (charL != charR) {
      return false
    }

    left++
    right--
  }

  return true
}

使用

function main() {
  // const s = 'A man, a plan, a canal: Panama'
  const s = 'race a car'

  console.log('[]:', isPalindrome(s))
}

main()

export {}